package com.dexter.year2023.charpter1_linkedlist.level2.topic2_3合并有序链表;

import com.dexter.year2023.charpter1_linkedlist.level1.Demo1.Node;

import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.initLinkedList;
import static com.dexter.year2023.charpter1_linkedlist.level1.Demo1.printLinkedList;

/**
 * LeetCode 21. 合并两个有序链表
 * https://leetcode.cn/problems/merge-two-sorted-lists/
 * <p>
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有结点组成的。
 * <p>
 * 示例 1：
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 * <p>
 * 提示：
 * 两个链表的结点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * l1 和 l2 均按 非递减顺序 排列
 *
 * @author Dexter
 */
public class Demo1MergeList {
    /**
     * 链表合并，求两个链表的并集 ★
     */
    public static void main(String[] args) {
        // 测试合并两个有序链表
        int[] a = {1, 3, 5, 7, 8, 9};
        int[] b = {1, 2, 4, 6, 8};
        Node l1 = initLinkedList(a);
        Node l2 = initLinkedList(b);
        Node head = mergeTwoLists(l1, l2);
        printLinkedList(head);

        // 测试合并K个有序链表
        int[] c = {1, 2, 2, 5, 6};
        int[] d = {3, 8, 10, 11};
        Node l3 = initLinkedList(c);
        Node l4 = initLinkedList(d);
        Node l5 = null;
        int[] e = {4, 4, 5, 5};
        Node l6 = initLinkedList(e);
        Node[] larray = {l3, l4, l5, l6};
        head = mergeKLists(larray);
        printLinkedList(head);
    }

    /**
     * 合并两个有序链表，最优写法
     *
     * @param list1
     * @param list2
     * @return
     */
    private static Node mergeTwoLists(Node list1, Node list2) {
        // 虚拟结点
        Node newNode = new Node(-1);
        Node res = newNode;
        while (list1 != null && list2 != null) {
            // list1.val 小
            if (list1.val < list2.val) {
                res.next = list1;
                list1 = list1.next;
            } else {
                // list1.val 大于等于 list2.val
                res.next = list2;
                list2 = list2.next;
            }
            // 移动新结点
            res = res.next;
        }
        res.next = list1 == null ? list2 : list1;
        return newNode.next;
    }

    /**
     * 合并K个有序链表
     *
     * @param lists
     * @return
     */
    private static Node mergeKLists(Node[] lists) {
        Node res = null;
        for (Node list : lists) {
            res = mergeTwoLists(res, list);
        }
        return res;
    }
}
